package com.javaDemo.ti;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName: Zidianshu2
 * @Auther: csy
 * @Date: 2021/6/22 15:09
 * @Description:
 */
public class Zidianshu2 {
    public static void main(String[] args) {
        // String[] a = {"looked", "just", "like", "her", "brother"};
        // String sentence = "jesslookedjustliketimherbrother";
        String[] a = {"im", "boy"};
        String sentence = "imisboy";
        int as = res(a, sentence);
        System.out.println(as);
    }
        public static int respace(String[] dictionary, String sentence) {
            // 构建字典树
            Trie trie = new Trie();
            for (String word: dictionary) {
                trie.insert(word);
            }
            // 状态转移，dp[i] 表示字符串的前 i 个字符的最少未匹配数
            int n = sentence.length();
            int[] dp = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                dp[i] = dp[i - 1] + 1;
                for (int idx: search(sentence, i - 1)) {
                    dp[i] = Math.min(dp[i], dp[idx]);
                }
            }
            return dp[n];
        }

    // 找到 sentence 中以 endPos 为结尾的单词，返回这些单词的开头下标。
    public static List<Integer> search(String sentence, int endPos) {
        List<Integer> indices = new ArrayList<>();
        TrieNode cur = root;
        for (int i = endPos; i >= 0; i--) {
            int c = sentence.charAt(i) - 'a';
            if (cur.children[c] == null) {
                break;
            }
            cur = cur.children[c];
            if (cur.isWord) {
                indices.add(i);
            }
        }
        return indices;
    }

    static TrieNode root;

    static class Trie {

        public Trie() {
            root = new TrieNode();
        }

        // 将单词倒序插入字典树
        public void insert(String word) {
            TrieNode cur = root;
            for (int i = word.length() - 1; i >= 0; i--) {
                int c = word.charAt(i) - 'a';
                if (cur.children[c] == null) {
                    cur.children[c] = new TrieNode();
                }
                cur = cur.children[c];
            }
            cur.isWord = true;
        }

    }

    static class TrieNode {
        boolean isWord;
        TrieNode[] children = new TrieNode[26];

        public TrieNode() {}
    }

    public static int res(String[] dic,String sen){
        int[] dp=new int[sen.length()+1];
        int right=1;
        while(right<=sen.length()){
            dp[right]=dp[right-1];
            for(String word:dic){
                if(right<word.length()){
                    continue;
                }
                String temp=sen.substring(right-word.length(),right);
                if(!temp.equals(word)){
                    continue;
                }
                dp[right]=Math.max(dp[right],dp[right-word.length()]+word.length());
            }
            right++;
        }
        return sen.length()-dp[sen.length()];
    }
}
